package com.monkeyboy.point;

import java.util.ArrayList;

/**
 * 题目：
 *  输出所有和为S的连续正数序列。序列内按照从小至大的顺序，序列间按照开始数字从小到大的顺序
 *  9-->[[2,3,4],[4,5]]
 *
 *  解题思路：
 *      首先审题要求连续的序列，所以可以定义两个指针，一个从start开始，一个就从end=start+1开始循环,如果start加到end的值小于数字s那么
 *      end++,如果大于s，那么就start++，如果等于的话那么就找到了
 * @Author Gavin
 * @date 2021.04.06 09:56
 */
public class Point2 {
    /**
     *这种方式性能不是很好
     */
    public static ArrayList<ArrayList<Integer>> FindContinuousSequence(int sum) {
        ArrayList<ArrayList<Integer>> result = new ArrayList<>();
        if (sum <= 1) {
            ArrayList<Integer> pre = new ArrayList<>();
            pre.add(sum);
            result.add(pre);
            return result;
        }
        for (int i = 1; i < sum - 1; i++) {
            int preSum = i;
            ArrayList<Integer> pre = new ArrayList<>();
            pre.add(i);
            for (int j = i + 1; j < sum - 1; j++) {
                pre.add(j);
                preSum = preSum + j;
                if (preSum == sum) {
                    result.add(pre);
                    break;
                }else if(preSum>sum){
                    break;
                }
            }
        }
        return result;
    }
    //这种方式性能比上面的好，因为它保存了连续序列的和，这样就不用每次从头开始计算总和
    public ArrayList<ArrayList<Integer>> FindContinuousSequence2(int sum) {
        ArrayList<ArrayList<Integer>> ret = new ArrayList<>();
        int start = 1, end = 2;
        int curSum = 3;
        /**
         * 临界值：
         * 只要end的值小于sum就行
         */
        while (end < sum) {
            //因为是连续序列，如果curSum>sum说明连续子序列加起来的总和就大于sum了，这时候左指针需要向右移动一位
            if (curSum > sum) {
                curSum -= start;
                start++;
            } else if (curSum < sum) {//和上面情况相反，子序列总和小于的话右指针就需要右移动一位
                end++;
                curSum += end;
            } else {
                ArrayList<Integer> list = new ArrayList<>();
                for (int i = start; i <= end; i++)
                    list.add(i);
                ret.add(list);
                curSum -= start;
                start++;//左指针右移动一位
                end++;//右指针也右移动一位
                curSum += end;
            }
        }
        return ret;
    }
    public static void main(String[] args) {
        ArrayList<ArrayList<Integer>> arrayLists = FindContinuousSequence(100);
        for (ArrayList<Integer> pre : arrayLists) {
            for (Integer pre2 : pre) {
                System.out.print(" "+pre2);
            }
            System.out.println("");
        }
        System.out.println(9 +10+ 11+ 12 +13 +14 +15 +16);
    }
}
